#include <vector>
#include <algorithm>
#include <limits.h> //INT_MAX
using namespace std;
class Solution {
public:
    // int Min(int a,int b,int c)
    // {
    //     multiset<int> array;
    //     array.emplace(a);
    //     array.emplace(b);
    //     array.emplace(c);
    //     return *(array.begin());
    // }
    int minFallingPathSum(vector<vector<int>>& matrix) {
        if(1 == matrix.size())
        return matrix[0][0];

        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> dp(n+1, vector<int>(m+2,INT_MAX));//多开一些空间，为了初始化dp时不越界
        for(int i = 0;i<m+2;++i)
        dp[0][i]=0;

        for(int i = 1;i<n+1;++i)
        {
            for(int j = 1;j<m+2-1;++j)
            {
                //dp[i][j] = Min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]) + matrix[i-1][j-1];
                dp[i][j] = min(min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1]) + matrix[i-1][j-1];
                //判断多个书中最小的值可以通过嵌套min求解
            }
        }
        int res = INT_MAX;
        for(int j = 1;j<m+2-1;j++)
        {
            if(res > dp[n][j])
            res = dp[n][j];
        }
        return res;
    }
};